/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年03月18日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
#include <map>
using namespace std;


class Solution {
public:
    int lenLongestFibSubseq(vector<int>& nums) {
        int size = nums.size();
        if(size <= 2){
            return 0;
        }
        
        map<int, int> dic;
        int ans = 0;
        dic[nums[0]] = 0;
        dic[nums[1]] = 1;
        for(int i = 2; i < size; i++){
            for(int j = i-1; j >= 1; j--){
                int length = 2;
                int x = nums[i], y = nums[j];
                int z;
                while(dic.find(x-y) != dic.end() && dic[y] > dic[x-y]){
                    length++;
                    z = x-y;
                    x = y;
                    y = z;
                    ans = max(ans, length);
                }


            }
            dic[nums[i]] = i;
        }

        return ans;
    }
};



class Solution {
public:
    int lenLongestFibSubseq(vector<int>& nums) {
        int size = nums.size();
        if(size <= 2){
            return 0;
        }
        
        map<int, int> dic;
        int ans = 0;
        dic[nums[size - 1]] = size - 1;
        dic[nums[size - 2]] = size - 2 ;
        for(int i = size -3; i >= 0; i--){
            for(int j = i + 1; j < size; j++){
                int length = 2;
                int x = nums[i], y = nums[j];
                while(dic.find(x+y) != dic.end()){
                    length++;
                    y = x+y;
                    x = y-x;
                }
                
                ans = max(ans, length);
            }

            dic[nums[i]] = i;
        }

        return ans > 2 ? ans : 0;
    }
};